Búsqueda de línea híbrida

Condiciones de terminación

\begin{equation} \| \nabla f(x_k)\|_2 < 10^{-8} \\ \| p_k \|_2 < 10^{-4}\\ \| x_{k-1}-x_k\|_2 < 10^{-5} \|x_{k-1}\|_2 \\ n_{iter}> 249 \end{equation}

Pruebas

Rosenbrock

In [21]:
resn, pathn = busqueda_linea(rosen, np.array([2,2]), direction='newton')
resm, pathm = busqueda_linea(rosen, np.array([2,2]), direction='max')
plot_path(0, 3, -2, 5, lambda x,y: 100*(y-x**2)**2+(x-1)**2, [1,1], pathn, pathm)

Converge bien en Newton (16 iteraciones) pero no en máximo descenso:

In [22]:
comparar(rosen, [2,2], 'newton', 0)
Método hibrido
    16 iteraciones (puntos pisados)
    18 iteraciones totales para encontrar alpha
    Error absoluto: 1.9020312854274676e-22
    Norma del gradiente: 5.797926033700089e-10
    ¿Hessiana definida positiva?: True

Método backtracking
    15 iteraciones (puntos pisados)
    20 iteraciones totales para encontrar alpha
    Error absoluto: 1.0706814636112183e-27
    Norma del gradiente: 2.5820771894751094e-13
    ¿Hessiana definida positiva?: True

Método interpol
    29 iteraciones (puntos pisados)
    47 iteraciones totales para encontrar alpha
    Error absoluto: 0.0
    Norma del gradiente: 0.0
    ¿Hessiana definida positiva?: True

In [23]:
comparar(rosen, [2,2], 'max', 0)
Método hibrido
    1 iteraciones (puntos pisados)
    2 iteraciones totales para encontrar alpha
    Error absoluto: 400.97718761859034
    Norma del gradiente: 1651.125202276957
    ¿Hessiana definida positiva?: True

Método backtracking
    250 iteraciones (puntos pisados)
    2734 iteraciones totales para encontrar alpha
    Error absoluto: 0.5024870441274595
    Norma del gradiente: 0.4741193290903157
    ¿Hessiana definida positiva?: True

Método interpol
    1 iteraciones (puntos pisados)
    2 iteraciones totales para encontrar alpha
    Error absoluto: 400.9943271014148
    Norma del gradiente: 1651.1683315314112
    ¿Hessiana definida positiva?: True

Rastrigin

In [24]:
resn, pathn = busqueda_linea(rastrigin, np.array([0.4, 0.3]), direction='newton')
resm, pathm = busqueda_linea(rastrigin, np.array([0.4, 0.3]), direction='max')
plot_path(-4, 4, -4, 4, lambda x,y: 20+x**2+y**2-10*np.cos(2*np.pi*x)-10*np.cos(2*np.pi*y), [0,0], pathn, pathm)

Se va a mínimos locales en ambos casos, pero igual es mejor el de máximo descenso.

In [25]:
comparar(rastrigin, [0.4, 0.3], 'max', 0)
Método hibrido
    15 iteraciones (puntos pisados)
    93 iteraciones totales para encontrar alpha
    Error absoluto: 9.949560298682503
    Norma del gradiente: 0.0002847154495140465
    ¿Hessiana definida positiva?: True

Método backtracking
    19 iteraciones (puntos pisados)
    165 iteraciones totales para encontrar alpha
    Error absoluto: 7.959662391640073
    Norma del gradiente: 0.0028880936340078336
    ¿Hessiana definida positiva?: True

Método interpol
    8 iteraciones (puntos pisados)
    32 iteraciones totales para encontrar alpha
    Error absoluto: 7.959662381108178
    Norma del gradiente: 5.886626313876674e-07
    ¿Hessiana definida positiva?: True

In [26]:
comparar(rastrigin, [0.4, 0.3], 'newton', 0)
Método hibrido
    5 iteraciones (puntos pisados)
    5 iteraciones totales para encontrar alpha
    Error absoluto: 21.246232048083407
    Norma del gradiente: 2.0758067189737618e-12
    ¿Hessiana definida positiva?: False

Método backtracking
    5 iteraciones (puntos pisados)
    6 iteraciones totales para encontrar alpha
    Error absoluto: 21.246232048083407
    Norma del gradiente: 2.0758067189737618e-12
    ¿Hessiana definida positiva?: False

Método interpol
    4 iteraciones (puntos pisados)
    45 iteraciones totales para encontrar alpha
    Error absoluto: 21.246232048083407
    Norma del gradiente: 1.4236912322732654e-09
    ¿Hessiana definida positiva?: False

Griewank

In [27]:
resn, pathn = busqueda_linea(griewank, np.array([0.4, 0.3]), direction='newton')
resm, pathm = busqueda_linea(griewank, np.array([0.4, 0.3]), direction='max')
plot_path(-4, 4, -1, 1, lambda x,y: (x**2+y**2)/4000-np.cos(x)-np.cos(y/np.sqrt(2))+1, [0,0], pathn, pathm)

No converge al mínimo global.

In [28]:
comparar(griewank, [2,0], 'newton', 0)
Método hibrido
    250 iteraciones (puntos pisados)
    5000 iteraciones totales para encontrar alpha
    Error absoluto: 1.9997657515249214
    Norma del gradiente: 0.07345859762521041
    ¿Hessiana definida positiva?: False

Método backtracking
    1 iteraciones (puntos pisados)
    21 iteraciones totales para encontrar alpha
    Error absoluto: 1.4171487378094147
    Norma del gradiente: 0.910296558696437
    ¿Hessiana definida positiva?: False

Método interpol
    3 iteraciones (puntos pisados)
    63 iteraciones totales para encontrar alpha
    Error absoluto: 2.0024686354182357
    Norma del gradiente: 5.662764158903559e-12
    ¿Hessiana definida positiva?: False

In [29]:
comparar(griewank, [2,0], 'max', 0)
Método hibrido
    5 iteraciones (puntos pisados)
    5 iteraciones totales para encontrar alpha
    Error absoluto: 0.0
    Norma del gradiente: 3.207949331562903e-10
    ¿Hessiana definida positiva?: True

Método backtracking
    5 iteraciones (puntos pisados)
    5 iteraciones totales para encontrar alpha
    Error absoluto: 0.0
    Norma del gradiente: 3.207949331562903e-10
    ¿Hessiana definida positiva?: True

Método interpol
    5 iteraciones (puntos pisados)
    5 iteraciones totales para encontrar alpha
    Error absoluto: 0.0
    Norma del gradiente: 3.207949331562903e-10
    ¿Hessiana definida positiva?: True

Ackley

In [30]:
resm, pathm = busqueda_linea(ackley, np.array([0, 1.5]), direction='max')
resn, pathn = busqueda_linea(ackley, np.array([0, 1.5]), direction='newton')
ack = lambda x,y: -20*np.exp(-0.2/2*(x**2+y**2))-np.exp(1/2*(np.cos(2*np.pi*x))+np.cos(2*np.pi*y))+20+np.exp(1)
plot_path(-1, 1, -2, 2, ack, [0,0], pathn, pathm)

Converge en máximo descenso pero no en Newton.

In [31]:
comparar(ackley, [0, 1.5], 'max', 0)
Método hibrido
    250 iteraciones (puntos pisados)
    596 iteraciones totales para encontrar alpha
    Error absoluto: 7.991167733978344e-05
    Norma del gradiente: 0.0010731414684836292
    ¿Hessiana definida positiva?: True

Método backtracking
    14 iteraciones (puntos pisados)
    84 iteraciones totales para encontrar alpha
    Error absoluto: 4.8874380542685e-08
    Norma del gradiente: 6.565128451534153e-07
    ¿Hessiana definida positiva?: True

Método interpol
    250 iteraciones (puntos pisados)
    508 iteraciones totales para encontrar alpha
    Error absoluto: 4.094411112776086e-05
    Norma del gradiente: 0.0005499136182511599
    ¿Hessiana definida positiva?: True

In [32]:
comparar(ackley, [0, 1.5], 'newton', 0)
Método hibrido
    250 iteraciones (puntos pisados)
    5000 iteraciones totales para encontrar alpha
    Error absoluto: 5.668459570618797
    Norma del gradiente: 0.1853727347721762
    ¿Hessiana definida positiva?: False

Método backtracking
    1 iteraciones (puntos pisados)
    21 iteraciones totales para encontrar alpha
    Error absoluto: 5.541124207560927
    Norma del gradiente: 2.287793424185262
    ¿Hessiana definida positiva?: False

Método interpol
    3 iteraciones (puntos pisados)
    63 iteraciones totales para encontrar alpha
    Error absoluto: 5.669249530986374
    Norma del gradiente: 1.2754842080140425e-09
    ¿Hessiana definida positiva?: False

Branin

In [33]:
resn, pathn = busqueda_linea(branin, np.array([-4, 13]), direction='newton')
resm, pathm = busqueda_linea(branin, np.array([-4, 13]), direction='max')
bran = lambda x,y: (y-(5.1/(4*np.pi**2))*x**2+(5/np.pi)*x-6)**2 + 10*(1-(1/(8*np.pi)))*np.cos(x)+10
plot_path(-5, 5, 10, 15, bran, [-np.pi,12.275], pathn, pathm) 

Converge al mínimo global en 62 iteraciones con máximo descenso y en 4 con Newton.

In [34]:
comparar(branin, [-4, 13], 'newton', 0.39789)
Método hibrido
    4 iteraciones (puntos pisados)
    4 iteraciones totales para encontrar alpha
    Error absoluto: 2.642270261865587e-06
    Norma del gradiente: 8.249413606590028e-15
    ¿Hessiana definida positiva?: True

Método backtracking
    4 iteraciones (puntos pisados)
    4 iteraciones totales para encontrar alpha
    Error absoluto: 2.642270261865587e-06
    Norma del gradiente: 8.249413606590028e-15
    ¿Hessiana definida positiva?: True

Método interpol
    4 iteraciones (puntos pisados)
    4 iteraciones totales para encontrar alpha
    Error absoluto: 2.642270261865587e-06
    Norma del gradiente: 8.249413606590028e-15
    ¿Hessiana definida positiva?: True

In [35]:
comparar(branin, [-4, 13], 'max', 0.39789)
Método hibrido
    62 iteraciones (puntos pisados)
    125 iteraciones totales para encontrar alpha
    Error absoluto: 2.1708060093383885e-06
    Norma del gradiente: 0.0011270208200181747
    ¿Hessiana definida positiva?: True

Método backtracking
    73 iteraciones (puntos pisados)
    324 iteraciones totales para encontrar alpha
    Error absoluto: 2.3269942396875187e-06
    Norma del gradiente: 0.0008911922620369977
    ¿Hessiana definida positiva?: True

Método interpol
    69 iteraciones (puntos pisados)
    139 iteraciones totales para encontrar alpha
    Error absoluto: 2.1247442753558055e-06
    Norma del gradiente: 0.0010567900571462794
    ¿Hessiana definida positiva?: True

Easom

In [36]:
resn, pathn = busqueda_linea(easom, np.array([5, 5]), direction='newton')
resm, pathm = busqueda_linea(easom, np.array([5, 5]), direction='max')
eas = lambda x,y: -np.cos(x)*np.cos(y)*np.exp(-(x-np.pi)**2-(y-np.pi)**2)
plot_path(2, 6, 2, 6, eas, [np.pi,np.pi], pathn, pathm) 

En ambos casos se atora y casi no avanza.

In [37]:
comparar(easom, [5,5], 'max', -1)
Método hibrido
    1 iteraciones (puntos pisados)
    1 iteraciones totales para encontrar alpha
    Error absoluto: 0.9999195021439116
    Norma del gradiente: 3.824027924812036e-05
    ¿Hessiana definida positiva?: True

Método backtracking
    1 iteraciones (puntos pisados)
    1 iteraciones totales para encontrar alpha
    Error absoluto: 0.9999195021439116
    Norma del gradiente: 3.824027924812036e-05
    ¿Hessiana definida positiva?: True

Método interpol
    1 iteraciones (puntos pisados)
    1 iteraciones totales para encontrar alpha
    Error absoluto: 0.9999195021439116
    Norma del gradiente: 3.824027924812036e-05
    ¿Hessiana definida positiva?: True

In [38]:
comparar(easom, [5,5], 'newton', -1)
Método hibrido
    3 iteraciones (puntos pisados)
    3 iteraciones totales para encontrar alpha
    Error absoluto: 0.9999188977610843
    Norma del gradiente: 7.518022531585278e-13
    ¿Hessiana definida positiva?: True

Método backtracking
    3 iteraciones (puntos pisados)
    3 iteraciones totales para encontrar alpha
    Error absoluto: 0.9999188977610843
    Norma del gradiente: 7.518022531585278e-13
    ¿Hessiana definida positiva?: True

Método interpol
    3 iteraciones (puntos pisados)
    3 iteraciones totales para encontrar alpha
    Error absoluto: 0.9999188977610843
    Norma del gradiente: 7.518022531585278e-13
    ¿Hessiana definida positiva?: True

Segunda función de schaffer (2)

In [39]:
resn, pathn = busqueda_linea(second_schaffer, np.array([1, 1]), direction='newton')
resm, pathm = busqueda_linea(second_schaffer, np.array([1, 1]), direction='max')
sha2 = lambda x,y: 0.5 + (np.sin(x**2-y**2)**2-0.5)/(1+0.001*(x**2+y**2))**2
plot_path(-2, 2, -2, 2, sha2, [0,0], pathn, pathm) 

Newton converge rápido (en 2 iteraciones) y máximo no converge.

In [40]:
comparar(second_schaffer, [1,1], 'newton', 0)
Método hibrido
    2 iteraciones (puntos pisados)
    2 iteraciones totales para encontrar alpha
    Error absoluto: 0.0
    Norma del gradiente: 6.041888845386573e-11
    ¿Hessiana definida positiva?: True

Método backtracking
    2 iteraciones (puntos pisados)
    2 iteraciones totales para encontrar alpha
    Error absoluto: 0.0
    Norma del gradiente: 6.041888845386573e-11
    ¿Hessiana definida positiva?: True

Método interpol
    2 iteraciones (puntos pisados)
    2 iteraciones totales para encontrar alpha
    Error absoluto: 0.0
    Norma del gradiente: 6.041888845386573e-11
    ¿Hessiana definida positiva?: True

In [41]:
comparar(second_schaffer, [1,1], 'max', 0)
Método hibrido
    250 iteraciones (puntos pisados)
    250 iteraciones totales para encontrar alpha
    Error absoluto: 0.0007370074220333089
    Norma del gradiente: 0.0017141357166399614
    ¿Hessiana definida positiva?: True

Método backtracking
    250 iteraciones (puntos pisados)
    250 iteraciones totales para encontrar alpha
    Error absoluto: 0.0007370074220333089
    Norma del gradiente: 0.0017141357166399614
    ¿Hessiana definida positiva?: True

Método interpol
    250 iteraciones (puntos pisados)
    250 iteraciones totales para encontrar alpha
    Error absoluto: 0.0007370074220333089
    Norma del gradiente: 0.0017141357166399614
    ¿Hessiana definida positiva?: True

Shubert

In [42]:
resn, pathn = busqueda_linea(shubert, np.array([3, 1]), direction='newton')
resm, pathm = busqueda_linea(shubert, np.array([3, 1]), direction='max')
def shub(x,y):
    resx = resy = 0
    for i in range(1,6):
        resx += i*np.cos((i+1)*x+i)
        resy += i*np.cos((i+1)*y+i)
    return resx*resy
plot_path(0, 45, 0, 6, shub, [36.27,5.48], pathn, pathm) 

En máximo descenso converge al mínimo global, en Newton a un local.

In [43]:
comparar(shubert, [1,2], 'max', -186.7309)
Método hibrido
    61 iteraciones (puntos pisados)
    580 iteraciones totales para encontrar alpha
    Error absoluto: 0.003339219275119376
    Norma del gradiente: 5.584063730986149
    ¿Hessiana definida positiva?: True

Método backtracking
    12 iteraciones (puntos pisados)
    113 iteraciones totales para encontrar alpha
    Error absoluto: 7.118507454606515e-06
    Norma del gradiente: 0.12506160293912852
    ¿Hessiana definida positiva?: True

Método interpol
    11 iteraciones (puntos pisados)
    50 iteraciones totales para encontrar alpha
    Error absoluto: 140.2195857670354
    Norma del gradiente: 0.01015741489901536
    ¿Hessiana definida positiva?: True

In [44]:
comparar(shubert, [1,2], 'newton', -186.7309)
Método hibrido
    4 iteraciones (puntos pisados)
    4 iteraciones totales para encontrar alpha
    Error absoluto: 186.7309
    Norma del gradiente: 2.8731249840155636e-13
    ¿Hessiana definida positiva?: False

Método backtracking
    4 iteraciones (puntos pisados)
    4 iteraciones totales para encontrar alpha
    Error absoluto: 186.7309
    Norma del gradiente: 2.8731249840155636e-13
    ¿Hessiana definida positiva?: False

Método interpol
    4 iteraciones (puntos pisados)
    4 iteraciones totales para encontrar alpha
    Error absoluto: 186.7309
    Norma del gradiente: 2.8731249840155636e-13
    ¿Hessiana definida positiva?: False